﻿#pragma once
//红黑树 
#include <iostream>
using namespace std;

//枚举颜色
enum Colour
{
	RED,
	BLACK
};

//对 map 和 set 封装
template <class Value>
struct rb_tree_node
{
	typedef rb_tree_node<Value> rb_node;
	
	rb_tree_node(const Value& data)
		:_data(data)
		, _left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)

	{}

	//节点值
	Value _data;
	//Ptr
	rb_node* _left;
	rb_node* _right;
	rb_node* _parent;
	Colour _col;
 };


// 迭代器
template <class T, class Ref , class Ptr>
struct rb_tree_iterator
{
	typedef rb_tree_node<T> Node;

	rb_tree_iterator(Node* node , Node* root)
		:_node(node)
		,__root(root)
	{}
	

	Node* _node;
	Node* __root;
	typedef rb_tree_iterator<T, Ref, Ptr>  Self;
	// ++ -- * -> != == 
	//返回的是数据的引用
	Ref operator*()
	{
		return _node->_data;
	}

	//返回的是数据的地址
	Ptr operator->()
	{
		return &_node->_data;
	}

	//返回的是迭代器
	Self operator++()
	{
		if (_node->_right)
		{
			// 右子树的最左节点
			Node* leftMost = _node->_right;
			while (leftMost && leftMost->_left)
			{
				leftMost = leftMost->_left;
			}

			 _node = leftMost;
		}

		else
		{
			//孩子为父亲的左的祖先
			Node* cur = _node;
			Node* parent = cur->_parent;

			while (parent && cur == parent->_right)
			{
				cur = parent;
				parent = cur->_parent;
			}

			_node = parent;
		}
		return *this;
	}

	//返回的是迭代器
	Self operator--()
	{
		if (_node == nullptr) // end()
		{
			// --end()，特殊处理，走到中序最后一个结点，整棵树的最右结点
			Node* rightMost = __root;
			while (rightMost && rightMost->_right)
			{
				rightMost = rightMost->_right;
			} 
			_node = rightMost;
		} 
		else if (_node->_left)
		{
			// 左子树不为空，中序左子树最后⼀个
			Node* rightMost = _node->_left;
			while (rightMost->_right)
			{
				rightMost = rightMost->_right;
			} 
			_node = rightMost;
		}
		else
		{
			// 孩子是父亲右的那个祖先
			Node* cur = _node;
			Node* parent = cur->_parent;
			while (parent && cur == parent->_left)
			{
				cur = parent;
				parent = cur->_parent;
			}
			_node = parent;
		}

		return *this;
	}

	bool operator!=(const Self& sef)
	{
		return _node != sef._node;
	}

	bool operator==(const Self& sef)
	{
		return _node == sef._node;
	}

};


// K/V
//map 和 set 要用同一个模版 , map 的key 要求第一个,所以这里加上仿函数
template <class Key , class Value , class KeyOfValue>
class rb_tree
{
	typedef rb_tree_node<Value> rb_node;
public:

	KeyOfValue key;

	typedef rb_tree_iterator<Value, Value&, Value*> Iterator;
	typedef rb_tree_iterator<Value, const Value&, const Value*> ConstIterator;


	Iterator Begin()
	{
		//整颗树最左节点
		rb_node* leftMost = _root;
		while (leftMost && leftMost->_left)
		{
			leftMost = leftMost->_left;
		}

		return Iterator(leftMost, _root);
	}

	Iterator End()
	{
		return Iterator(nullptr, _root);
	}

	ConstIterator Begin() const 
	{
		//整颗树最左节点
		rb_node* leftMost = _root;
		while (leftMost && leftMost->_left)
		{
			leftMost = leftMost->_left;
		}

		return Iterator(leftMost, _root);

	}

	ConstIterator End()  const
	{
		return Iterator(nullptr, _root);
	}


	//Insert
	pair<Iterator,bool> Insert(const Value& data)
	{

		if (_root == nullptr)
		{
			_root = new rb_node(data);
			_root->_col = BLACK;

			return { Iterator(_root,_root), true };
		}

		rb_node* cur = _root;
		rb_node* parent = nullptr;
		while (cur)
		{
			if (key(data) > key(cur->_data))
			{
				parent = cur;
				cur = cur->_right;
			}
			else if(key(data) < key(cur->_data))
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return { Iterator(cur,_root),false };
			}
		}

		//cur == nullptr - > 插入
		//红黑树要求插入为红
		cur = new rb_node(data);
		rb_node* newnode = cur;
		cur->_col = RED;
		if (key(parent->_data) < key(data))
			parent->_right = cur;
		else 
			parent->_left = cur;

		cur->_parent = parent;

		//更新
		while (parent && parent->_col == RED)
		{
			rb_node* grandfather = parent->_parent;
			if (parent == grandfather->_left)
			{
				//   g 
				//  p u
				// c
				rb_node* uncle = grandfather->_right;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					//Up 
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					//旋转 + 变色
					//   g 
					//  p u
					// c
					if (cur == parent->_left)
					{
						//右单
						RotateR(grandfather);

						//变色
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//   g 
						//  p u
						//   c

						// L R
						RotateL(parent);
						RotateR(grandfather);
							
						//变色
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
					break;
				}
			}
			else
			{
				//   g 
				//  u  p 
				// c
				rb_node* uncle = grandfather->_left;
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					grandfather->_col = RED;

					//Up 
					cur = grandfather;
					parent = cur->_parent;
				}
				else
				{
					//旋转 + 变色
					//   g 
					//  u  p 
					//      c
					if (cur == parent->_right)
					{
						//左单
						RotateL(grandfather);

						//变色
						parent->_col = BLACK;
						grandfather->_col = RED;
					}
					else
					{
						//   g 
						//  u  p 
						//    c

						// R L
						RotateR(parent);
						RotateL(grandfather);

						//变色
						cur->_col = BLACK;
						grandfather->_col = RED;
					}
				}
				break;
			}
		}

		_root->_col = BLACK;
		return{ Iterator(newnode, _root), true };
	}

	void RotateL(rb_node* parent)
	{
		rb_node* subR = parent->_right;
		rb_node* subRL = subR->_left;
		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

		rb_node* parentParent = parent->_parent;
		subR->_left = parent;
		parent->_parent = subR;
		if (parentParent == nullptr)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (parent == parentParent->_left)
			{
				parentParent->_left = subR;
			}
			else
			{
				parentParent->_right = subR;
			}
			subR->_parent = parentParent;
		}
	}

	void RotateR(rb_node* parent)
	{
		rb_node* subL = parent->_left;
		rb_node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		rb_node* pParent = parent->_parent;

		subL->_right = parent;
		parent->_parent = subL;

		if (parent == _root)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (pParent->_left == parent)
			{
				pParent->_left = subL;
			}
			else
			{
				pParent->_right = subL;
			}

			subL->_parent = pParent;
		}
	}

private:
	//底层是节点的封装
	rb_node* _root = nullptr;
};